1320. Лес

Утро в сосновом лесу. 1889. Быть может, самая популярная картина Шишкина — «Утро в сосновом лесу». В ней он стремится передать очарование нетронутой девственной природы, поэтизируя жизнь леса.

Медведи написаны другом художника К.А. Савицким. Они получились столь удачно, что Савицкий даже расписался вместе с Шишкиным на картине. Однако П.М. Третьяков, купив картину, снял подпись. Он утвердил авторство одного Шишкина. Ведь в картине, говорил меценат, «начиная от замысла и кончая исполнением, все говорит о манере живописи, о творческом методе, свойственных именно Шишкину».

Рассмотрим простую модель роста деревьев в сосновом лесу. Все деревья разделим на четыре группы: молодые саженцы (возрастная группа от 0 до 15 лет), молодые деревья (от 16 до 30 лет), средневозрастные деревья (от 31 до 45 лет) и старые (старше 45 лет). Длительность одного периода времени составляет 15 лет. В задаче необходимо определить количественное изменение популяции деревьев, если:

1. Определенный процент каждой группы деревьев погибает;

2. Выжившие деревья одной группы переходят в следующую возрастную группу. Старые деревья остаются старыми;

3. Умершие деревья заменяются молодыми саженцами. Таким образом, количество деревьев в лесу остается неизменным.

Известно, что изначально лес состоит из n молодых саженцев. Известен процент деревьев, который погибает за один период времени в каждой возрастной группе: p_baby, p_young, p_middle-age, p_old. Необходимо определить среднее значение количества деревьев в каждой группе через 15k лет.

Вход. Каждая строка является отдельным тестом и содержит 6 целочисленных значений: n (10 < n < 100000), k (1 ≤ k ≤ 100), p_baby, p_young, p_middle-age, p_old. (0 ≤ p_baby, p_young, p_middle-age, p_old ≤ 100).

Выход. Для каждого теста вывести в отдельной строке 4 значения – среднее число деревьев в каждой группе через 15k лет. Все числа выводить с 6 знаками после десятичной запятой.

Пример входа

50000 1 10 20 30 40

50000 2 10 20 30 40

50000 3 10 20 30 40

50000 100 10 20 30 40

Пример выхода

5000.000000 45000.000000 0.000000 0.000000

9500.000000 4500.000000 36000.000000 0.000000

12650.000000 8550.000000 3600.000000 25200.000000

12886.597938 11597.938144 9278.350515 16237.113402

РЕШЕНИЕ

теория вероятности

Анализ алгоритма

Обозначим через b(k), y(k), m(k), o(k) количество деревьев соответственных возрастных групп через 15k лет. Значения p_baby, p_young, p_middle-age, p_old сразу поделим на 100, получив части умирающих деревьев в каждой группе.

Тогда согласно условию задачи, получим следующие соотношения:

b(k + 1) = p_baby * b(k) + p_young * y(k) + p_middle-age * m(k) + p_old * o(k)

y(k + 1) = (1 – p_baby) * b(k)

m(k + 1) = (1 – p_young) * y(k)

o(k + 1) = (1 – p_middle-age) * m(k) + (1 – p_old) * o(k)

Обозначим вектор распределения деревьев через x(k) = (b(k), y(k), m(k), o(k)). Рассмотрим матрицу:

A =

Матрица А стохастическая, и x(k + 1) = A * x(k).

Изначально x(0) = (n, 0, 0, 0). Через 15k лет распределение деревьев составит

x(k) = A^k * x(0)

Например, для n = 50000, p_baby= 0,1, p_young = 0,2, p_middle-age = 0,3, p_old = 0,4, получим

x(k) =

x(0) = , x(1) = = ,

x(2) = = ,

x(3) = = ,

Для матрицы стабильным состоянием распределения деревьев будет

= .